/* dichotomy.h
 *
 *	Copyright (C) 2008 CRIMERE
 *	Copyright (C) 2008 Jean-Marc Mercier
 *	
 *	This file is part of OTS (optimally transported schemes), an open-source library
 *	dedicated to scientific computing. http://code.google.com/p/optimally-transported-schemes/
 *
 *	CRIMERE makes no representations about the suitability of this
 *	software for any purpose. It is provided "as is" without express or
 *	implied warranty.
 *
 *  This program is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation, either version 3 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *   You should have received a copy of the GNU General Public License
 *   along with this program.  If not, see <http://www.gnu.org/licenses/>.
 *
 *
 */
#pragma once
#include <list>


template<class Function, class I>
std::list<I> find_zeros(const Function &f, const I& searchrange, OS_double max_width = THRESHOLD)
{
  std::list<I> l, res;
  l.push_back(searchrange);
  while(!l.empty()) {
//	  std::cout << l << std::endl;
    I range = l.front();
    l.pop_front();
    I val = f(range);
    if (zero_in(val)) {
      if(width(range) < max_width ) {
		res.push_back(range);
        continue;
      }
      std::pair<I,I> p = bisect(range);
      l.push_back(p.first);
      l.push_back(p.second);
    }
  }
  return res;
};
